package leecoke;

import java.util.List;

// 删除链表倒数第 n 个节点
public class Test019 {

    public static class ListNode{
        int val;
        ListNode next;

        ListNode(int val) {
            val = val;
        }
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 构建一个哨兵节点，防止头节点被删除
        ListNode dumpy = new ListNode(0);
        dumpy.next = head;
        // 前指针
        ListNode pre = dumpy;
        // 后指针
        ListNode post = dumpy;
        // 前指针先走 n 个
        for (int i = 0; i < n; i++) {
            pre = pre.next;
        }
        // 前后指针同时后移
        // 当前指针为空时，后指针到达倒数n个节点
        while (post.next != null) {
            pre = pre.next;
            post = post.next;
        }
        post.next = post.next.next;
        return dumpy.next;
    }
}
